# 99. 分巧克力
# 好题，和k_bisearch3_lc34有些类似
# https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/?envType=study-plan-v2&envId=top-100-liked
# Date: 2025/1/16
from leetcode import test


def solution(k, chocolates):
    # 暴力法
    max_size = max(map(min, chocolates))
    res = 0
    for i in range(1, max_size):  # i为巧克力的尺寸
        choco_nums = 0
        for x, y in chocolates:
            if i > min(x, y):
                continue
            choco_nums += (x // i) * (y // i)
        if choco_nums >= k:
            res = max(res, i)
    return res


def solution_bisect(k, chocolates):
    max_size = max(map(min, chocolates))
    res = 0

    left, right = 0, max_size

    def can_divide(size):
        choco_nums = 0
        for x, y in chocolates:
            if size > min(x, y):
                continue
            choco_nums += (x // size) * (y // size)
            if choco_nums >= k:
                return True
        return False

    while left <= right:
        mid = (left + right) // 2
        if can_divide(mid):
            res = mid  # 当前 mid 是可行的，尝试更大的边长
            left = mid + 1
        else:
            right = mid - 1  # 当前 mid 不可行，尝试更小的边长
    return res


if __name__ == "__main__":
    # n, k = map(int, input().split())
    # chocolates = []
    # for i in range(n):
    #     chocolates.append(list(map(int, input().split())))
    #
    # print(deliver(k, chocolates))

    inp = [{"k": 10, "chocolates": [[6, 5], [5, 6]]},
           {"k": 10, "chocolates": [[6, 5], [5, 6], [5, 6], [5, 6], [5, 6], ]},
           {"k": 10, "chocolates": [[12, 15], [7, 8]]},
           {"k": 4, "chocolates": [[12, 15], [7, 8]]},
           {"k": 10, "chocolates": [[4, 7], [8, 6], [4, 6], [7, 3], [10, 2], [3, 8], [1, 10], [4, 7], [1, 7], [3, 7]]},
           ]
    out = [2, 3, 4, 6, 3]
    test.test_function(solution, inp, out)
    test.test_function(solution_bisect, inp, out)
